package org.basis.algorithm.greedy;

import java.util.PriorityQueue;

/**
 * 项目最大利润问题
 * 输入:
 * 正数数组costs
 * 正数数组profits
 * 正数k
 * 正数m
 * 含义:
 * costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你只能串行的最多做k个项目
 * m表示你初始的资金
 * 说明: 你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。 输出:
 * 你最后获得的最大钱数。
 *
 * @author Mr_wenpan@163.com 2021/12/27 17:02
 */
public class MaximumProfitOfProject {

    public static void main(String[] args) {

    }

    /**
     * 求最大利润
     *
     * @param costs   成本
     * @param profits 利润
     * @param k       最多做k个项目
     * @param m       启动资金
     * @return int
     * @author Mr_wenpan@163.com 2021/12/27 5:14 下午
     */
    public static int findMaxPrifit(int[] costs, int[] profits, int k, int m) {
        if (costs == null || profits == null || k <= 0) {
            return 0;
        }

        // 按花费组织的小根堆
        PriorityQueue<Project> queue = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        // 按利润组织的大根堆
        PriorityQueue<Project> queue2 = new PriorityQueue<>(((o1, o2) -> o2.profit - o1.profit));
        // 将数据构建为项目
        for (int i = 0; i < costs.length; i++) {
            queue.add(new Project(costs[i], profits[i]));
        }

        // 每次选择一个项目
        for (int i = 0; i < k; i++) {
            // 每次都从 按花费组织的小根堆 中拿出当前自己的资金能做的所有项目并放入按利润组织的大根堆
            while (!queue.isEmpty()) {
                Project poll = queue.poll();
                // 当前成本可以做这个项目
                if (poll.cost <= m) {
                    queue2.add(poll);
                } else {
                    // 压回去
                    queue.add(poll);
                    break;
                }
            }

            if (!queue2.isEmpty()) {
                Project poll = queue2.poll();
                // 更新成本
                m += poll.profit;
            }
        }

        return m;
    }

    /**
     * 项目
     */
    static class Project {
        /**
         * 成本
         */
        int cost;
        /**
         * 利润
         */
        int profit;

        public Project() {
        }

        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

}
